#!/usr/bin/env python
"""
Module grammar.
Authors: Stephane Vialette, Yu Zhou

"""

from string import upper
from networkx import DiGraph
from . import utils
from .automaton import *

###############################################################################

class Symbol(object):
    """
    Abstract class.
    """
    def __init__(self, name):
        self._name = upper(str(name)) # added str()

    def __repr__(self):
        """
        Return a concise string representation of this symbol. 
        """
        return '%s' % self

    def __hash__(self):
        """Hashable by name. Added 10/16/2008
        """
        return hash(self._name)

    def getName(self):
        """get name, inherited by Terminal, NonTerminal, InterNonTerminal.
        """
        return self._name

    def __eq__(self, other):
        """
        Return true if it is equal to other.
        """
        return (isinstance(other, self.__class__) and
                self._name == other._name)

    def __cmp__(self, other):
        if not isinstance(other, self.__class__):
            return -1
        return cmp(self._name, other._name)

###############################################################################     
    
class Terminal(Symbol):
    """
    Terminal symbol.
    """
    def __init__(self, name):
        super(Terminal, self).__init__(name)

    def __str__(self):
        """
        Return a verbose string representation of this terminal.
        """
        return 'T(\'%s\')' % self._name

###############################################################################

class NonTerminal(Symbol):
    """
    Non terminal symbol.
    """
    def __init__(self, name):
        super(NonTerminal, self).__init__(name)

    def __str__(self):
        """
        Return a verbose string representation of this non terminal.
        """
        return 'NT(%s)' % self._name

###############################################################################

class InterNonTerminal(NonTerminal):
    """
    NonTerminal Generator in Grammar intersection with DFA 
    """
    def generateName(lftLabel, nonTerminalNode, rgtLabel):
        """
        Generate name of an InterNonTerminal 
        """
        return "_".join([lftLabel, nonTerminalNode.getName(), rgtLabel])
    
    generateName = staticmethod(generateName)
    
    def __init__(self, lftLabel, nonTerminalNode, rgtLabel):
        if not isinstance(nonTerminalNode, NonTerminal):
            return None
        
        self._lftLabel = lftLabel
        self._nonTerminal = nonTerminalNode
        self._rgtLabel = rgtLabel
        self._name = InterNonTerminal.generateName(lftLabel, nonTerminalNode, 
                                                   rgtLabel)
        
    def __str__(self):
        """
        Return a verbose string representation of this Intersected Non-terminal
        """
        return 'I(\'%s\')' % self._name   
    
    def getLeftLabel(self):
        """Return _lftLabel
        """
        return self._lftLabel
    
    def getRightLabel(self):
        """Return _rgtLabel
        """
        return self._rgtLabel
    
    def getNonTerminal(self):
        """Return _nonTerminal
        """
        return self._nonTerminal

    def __eq__(self, other):
        """
        Return true if this InterNonTerminal is equal to other.
        """
        return (isinstance(other, self.__class__) and
                self._lftLabel == other._lftLabel and
                self._nonTerminal == other._nonTerminal and
                self._rgtLabel == other._rgtLabel)

    def __cmp__(self, other):
        """
        Compare this InterNonTerminal to other.
        """
        if not isinstance(other, self.__class__):
            return -1
        return cmp((self._lftLabel, self._nonTerminal, self._rgtLabel),
                   (other._lftLabel, other._nonTerminal, self._rgtLabel))
    
###############################################################################

class NonTerminalGenerator(object):
    """
    NonTerminal Generator
    """
    def __init__(self, prefix = "V"):
        self._prefix = prefix
        self._counter = 0

    def __call__(self):
        self._counter += 1
        label = self._prefix + str(self._counter)
        return NonTerminal(label)  
                
###############################################################################
    
class Production(object):
    """
    Production class
    """
    def __init__(self, leftHandSide, rightHandSide):
        if not isinstance(rightHandSide, list):
            raise TypeError("production right hand side should be ",
                              "a list")
        if not isinstance(leftHandSide, NonTerminal):
            raise TypeError("production left hand side should be ",
                              "a non terminal")
        for symbol in rightHandSide:
            if not isinstance(symbol, Symbol):
                raise TypeError("each right hand side element should be ",
                                  "a terminal or a non  terminal")
        self._leftHandSide  = leftHandSide
        self._rightHandSide = tuple(rightHandSide) # Not changable.

    def leftHandSide(self):
        """
        Return the left-hand side of this production.
        """
        return self._leftHandSide

    def rightHandSide(self):
        """
        Return the right-hand side of this production.
        """
        return self._rightHandSide

    def __repr__(self):
        """
        Return a concise string representation of this production. 
        """
        return '%s' % self

    def __str__(self):
        """
        Return a verbose string representation of this production.
        """
        strs = '%s ->' % (self._leftHandSide,)
        for symbol in self._rightHandSide:
            if isinstance(symbol, NonTerminal):
                strs += ' %s' % (symbol,)
            else:
                strs += ' %r' % (symbol,)
        return strs

    def __eq__(self, other):
        """
        Return true if this production is equal to other.
        """
        return (isinstance(other, self.__class__) and
                self._leftHandSide  == other._leftHandSide and
                self._rightHandSide == other._rightHandSide)
                 
    def __ne__(self, other):
        """
        Return true if this production is not equal to other.
        """
        return not (self == other)

    def __cmp__(self, other):
        """
        Compare this production to other.
        """
        if not isinstance(other, self.__class__):
            return -1
        return cmp((self._leftHandSide, self._rightHandSide),
                   (other._leftHandSide, other._rightHandSide))

    def __hash__(self):
        """Hashable. Added 10/16/2008
        """
        return hash((self._leftHandSide, self._rightHandSide))

###############################################################################
    
class Grammar(object):
    """
    A context-free grammar. A Grammar consists of a start state
    (the axiom) and a set of productions.
    """
    def __init__(self, axiom, productions):
        """
        Initialize a new context-free grammar, from the given axiom
        and set of Productions.
        """
        self._axiom = axiom
        self._productions = productions   # production list

        self._cleanRepeatProductions()    # keep single-copy production
        
        self._leftHandSideIndex  = dict() #'_leftHandSide' => [production,]
        self._rightHandSideIndex = dict() #'_rightHandSide[0]' => [production,]
        self._index()                     # do indexing
        
    def _cleanRepeatProductions(self):
        """
        Remove repeat productions
        """
        num_before = len(self._productions)
        new_productions = list(set(self._productions))
        self._productions = new_productions
        
        utils.info('remove repeat productions: before=%d, after=%d'
                   % (num_before, len(self._productions)))

    def _indexProduction(self, production):
        """
        Index a given production.
        """
        if production._leftHandSide not in self._leftHandSideIndex:
            self._leftHandSideIndex[production._leftHandSide] = []
        self._leftHandSideIndex[production._leftHandSide].append(production)
        
        if production._rightHandSide:
            if production._rightHandSide[0] not in self._rightHandSideIndex:
                self._rightHandSideIndex[production._rightHandSide[0]] = []
        if production._rightHandSide:
            self._rightHandSideIndex[production._rightHandSide[0]].append(
                                                                production)

    def _index(self):
        """
        Index all productions for quickly search.
        """
        for production in self._productions:
            self._indexProduction(production)

    def axiom(self):
        """
        Return the axiom of this grammar.
        """
        return self._axiom

    def productions(self, leftHandSide = None, rightHandSide = None):
        """
        Return the productions of this grammar specified by leftHandSide
        and the first Terminal/NonTerminal of the given rightHandSide.
        
        """
        if rightHandSide: assert isinstance(rightHandSide, tuple) 
        
        # no constraints so return everything
        if not leftHandSide and not rightHandSide:
            return self._productions

        # only leftHandSide specified so look up its index
        elif leftHandSide and not rightHandSide:
            if leftHandSide in self._leftHandSideIndex:
                return self._leftHandSideIndex[leftHandSide]
            else:
                return list()

        # only rightHandSide specified so look up its index
        elif rightHandSide and not leftHandSide:
            if rightHandSide[0] in self._rightHandSideIndex:
                return self._rightHandSideIndex[rightHandSide[0]]
            else:
                return list()

        # intersect
        else:
            if leftHandSide in self._leftHandSideIndex:
                return [prod for prod in self._leftHandSideIndex[leftHandSide]
                        if prod in self._rightHandSideIndex[rightHandSide[0]]]
            else:
                return list()

    def check_coverage(self, tokens):
        """
        Check whether this grammar rules cover the given list of tokens.
        If not, then raise an exception.
        """
        missing = [tok for tok in tokens
                   if len(self.productions(rightHandSide = tok)) == 0]
        if missing:
            missing = ', '.join('%r' % (w,) for w in missing)
            raise ValueError("Grammar does not cover some of the "
                               "input words: %r." + missing)

    def __repr__(self):
        """
        Return a concise string representation of this grammar. 
        """
        return '<Grammar with %d productions>' % len(self._productions)

    def __str__(self):
        """
        Return a verbose string representation of this grammar.
        """
        strs = 'Grammar with %d productions' % len(self._productions)
        strs += ' (axiom state = %s)' % self._axiom
        for production in sorted(self._productions):
            strs += '\n    %s' % production
        return strs

    ###############################################################################

    def num_nt(self):
        """
        Return number of NonTerminals
        """
        return len(self._leftHandSideIndex)
    
    def num_prod(self):
        """
        Return number of productions
        """
        return len(self._productions)

    ###############################################################################

    def toGenRGenS(self, outfile):
        """write Grammar to outfile in GenRGenS format
        """
        handle = open(outfile, 'w')    
        # default lines
        handle.write("""%s\n\n%s\n\n""" % 
                     ("TYPE = GRAMMAR", "SYMBOLS = WORDS"))
        
        # start
        handle.write("""START =%s\n\n""" % self._axiom._name)
                
        # rules
        rules = ""
        for p in sorted(self._productions): 
            strs = '  %s ->' % (p._leftHandSide._name,)
            for symbol in p._rightHandSide:
                strs += ' %s' % (symbol._name,)
                
            rules += strs + ";\n"       
        handle.write("""RULES =\n%s\n\n""" % rules)
        
        handle.close()

    ###############################################################################

    def intersect(self, dfa):
        """intersect with an automaton (DFA)
        """
        assert isinstance(dfa, DFA)
        
        # new Axiom
        nonGenerator = NonTerminalGenerator(prefix='S')
        newAxiom = nonGenerator()
        utils.debug('New Axiom generated: %s' % newAxiom)
        
        # generate new productions 
        newProductions  = list()
        newNonTerminalIndex = dict() # using Teminal/NonTerminal._name as key
        newNonTerminalQueue = list()
        
        # 1. newAxiom -> [dfa.initial, grammar.axiom, dfa.final] 
        for dfaInitial in dfa.getInitials():
            for dfaFinal in dfa.getFinals():
                # new nonTerminal
                newNonTerminal = InterNonTerminal(dfaInitial.getName(), 
                    self.axiom(), dfaFinal.getName())
                # add to queue
                newNonTerminalQueue.append(newNonTerminal)
                # add to index                
                newNonTerminalIndex[newNonTerminal.getName()] = newNonTerminal
                
                newProduction = Production(newAxiom, [newNonTerminal])  
                newProductions.append(newProduction)                                                             
                utils.debug('newProduction: %s' % newProduction)
                
        # add Terminals
        for label in dfa.getAlphabet():
            newTerminal = Terminal(upper(label))
            newNonTerminalIndex[newTerminal.getName()] = newTerminal

        # 2. V -> a, V -> a V1, V -> a V1 u, V -> a V1 u V2
        count = 0 
        while len(newNonTerminalQueue) > 0:
            count += 1

            utils.debug('count=%d, NTQueue=%d, count+NTQueue=%d' %
                        (count, len(newNonTerminalQueue), 
                         count+len(newNonTerminalQueue)))
            
            nt = newNonTerminalQueue.pop(0) # use list as queue
            utils.debug('pop nonTerminal: %s' % nt)
             
            # [q, V, qprime]
            newLeftHandSide = nt 
            q = dfa.getState(nt.getLeftLabel())
            qprime = dfa.getState(nt.getRightLabel())
            V = nt.getNonTerminal()                 
            
            for p in self._productions:                
                utils.debug('g: %s' % p)
                leftHandSide  = p.leftHandSide()
                rightHandSide = p.rightHandSide()
                
                # Only consider productions starting with nt's nonTerminal 
                if leftHandSide != V: continue
                
                # case 1: V0 -> V1
                # case 2: V0 -> u0 (A|G|C|U)
                if len(rightHandSide) == 1:
                    # V0 -> V1
                    if isinstance(rightHandSide[0], NonTerminal):
                        V1 = rightHandSide[0]
                        # Note: only for Initial NonTerminal. 
                        # Assume no V->V1 in which V is not Initial NonTerminal.
                        if q == dfa.getInitials()[0] and qprime in dfa.getFinals():
                            newNonTerminalName = InterNonTerminal.generateName(q.getName(), V1, qprime.getName())
                            if newNonTerminalName not in newNonTerminalIndex:
                                newNonTerminal = InterNonTerminal(q.getName(), V1, qprime.getName())
                                newNonTerminalQueue.append(newNonTerminal)
                                newNonTerminalIndex[newNonTerminal.getName()] = newNonTerminal
                                newRightHandSide = [newNonTerminal]
                            else:
                                newRightHandSide = [newNonTerminalIndex[newNonTerminalName]]
                            newProduction = Production(newLeftHandSide, newRightHandSide)  
                            newProductions.append(newProduction)                                                             
                            utils.debug('newProduction: %s' % newProduction)
 
                    # V0 -> u0 (A|G|C|U)    
                    else:
                        u0 = rightHandSide[0].getName()
                        for qOutTrans in q.getOutTransition():
                            if qOutTrans.getLabel() == u0 and qOutTrans.getSucc() == qprime:                            
                                # RightHandSide:
                                newRightHandSide = [newNonTerminalIndex[u0]]                                                                                                                                                                
                                
                                newProduction = Production(newLeftHandSide, newRightHandSide)  
                                newProductions.append(newProduction)                                                             
                                utils.debug('newProduction: %s' % newProduction)
                
                # case 3: V0 -> u0 V1
                # case 4: V0 -> u0 u1  
                if len(rightHandSide) == 2:
                    u0 = rightHandSide[0].getName()
                    # V0 -> u0 u1
                    if isinstance(rightHandSide[1], Terminal):
                        u1 = rightHandSide[1].getName()

                        #print q.getOutTransition(u0)[0].getSucc().getOutTransition(u1)[0].getSucc()
                        if (q.getOutTransition(u0) and q.getOutTransition(u0)[0].getSucc().getOutTransition(u1) 
                            and q.getOutTransition(u0)[0].getSucc().getOutTransition(u1)[0].getSucc() == qprime):
                            #print id(q.getOutTransition(u0)[0].getSucc().getOutTransition(u1)[0].getSucc())
                            newRightHandSide = [newNonTerminalIndex[u0], newNonTerminalIndex[u1]]
                            newProduction = Production(newLeftHandSide, newRightHandSide)  
                            newProductions.append(newProduction)
                            utils.debug('newProduction: %s' % newProduction)
                                                    
                    #V0 -> u0 V1    
                    else:
                        V1 = rightHandSide[1]                        
                        for qOutTrans in q.getOutTransition():
                            if qOutTrans.getLabel() == u0:
                                # RightHandSide:
                                newRightHandSide = None                            
                                newNonTerminalName = InterNonTerminal.generateName(qOutTrans.getSucc().getName(), V1, qprime.getName())
                                if newNonTerminalName not in newNonTerminalIndex:
                                    newNonTerminal = InterNonTerminal(qOutTrans.getSucc().getName(), V1, qprime.getName())
                                    newNonTerminalQueue.append(newNonTerminal)
                                    newNonTerminalIndex[newNonTerminal.getName()] = newNonTerminal
                                    newRightHandSide = [newNonTerminalIndex[u0], newNonTerminal]
                                else:
                                    newRightHandSide = [newNonTerminalIndex[u0], newNonTerminalIndex[newNonTerminalName]] 
                                    
                                newProduction = Production(newLeftHandSide, newRightHandSide)  
                                newProductions.append(newProduction)
                                utils.debug('newProduction: %s' % newProduction)
                                                                
                # case 5: V0 -> u0 V1 u1
                if len(rightHandSide) == 3:
                    u0 = rightHandSide[0].getName()
                    V1 = rightHandSide[1]
                    u1 = rightHandSide[2].getName()
                    
                    for qOutTrans in q.getOutTransition():
                        if qOutTrans.getLabel() == u0:
                            for qprimeInTrans in qprime.getInTransition(u1):
                                if qprimeInTrans.getLabel() == u1:
                                    # RightHandSide:
                                    newRightHandSide = None
                                    newNonTerminalName = InterNonTerminal.generateName(qOutTrans.getSucc().getName(), V1, qprimeInTrans.getPred().getName())
                                    if newNonTerminalName not in newNonTerminalIndex:
                                        newNonTerminal = InterNonTerminal(qOutTrans.getSucc().getName(), V1, qprimeInTrans.getPred().getName())
                                        newNonTerminalQueue.append(newNonTerminal)
                                        newNonTerminalIndex[newNonTerminal.getName()] = newNonTerminal
                                        newRightHandSide = [newNonTerminalIndex[u0], newNonTerminal, newNonTerminalIndex[u1]]
                                    else:
                                        newRightHandSide = [newNonTerminalIndex[u0], newNonTerminalIndex[newNonTerminalName], newNonTerminalIndex[u1]] 
                                    
                                    newProduction = Production(newLeftHandSide, newRightHandSide)  
                                    newProductions.append(newProduction)
                                    utils.debug('newProduction: %s' % newProduction)
                                                                                
                # case 6: V0 -> u0 V1 u1 V2
                if len(rightHandSide) == 4:
                    u0 = rightHandSide[0].getName()
                    V1 = rightHandSide[1]
                    u1 = rightHandSide[2].getName()   
                    V2 = rightHandSide[3]                     
                       
                    for qOutTrans in q.getOutTransition():
                        if qOutTrans.getLabel() == u0: # 
                            for qi in dfa.getStates():                           
                                for qiOutTrans in qi.getOutTransition():
                                    if qiOutTrans.getLabel() == u1:                                                                                    
                                        #utils.debug('newNonTerminalIndex: '+','.join(map(str, newNonTerminalIndex.keys())))
                                        # RightHandSide:
                                        newRightHandSide = None
                                        newNonTerminal1 = None
                                        newNonTerminal2 = None
                                        newNonTerminalName1 = InterNonTerminal.generateName(qOutTrans.getSucc().getName(), V1, qi.getName())
                                        if newNonTerminalName1 not in newNonTerminalIndex:
                                            newNonTerminal1 = InterNonTerminal(qOutTrans.getSucc().getName(), V1, qi.getName())
                                            newNonTerminalQueue.append(newNonTerminal1)                                                
                                            newNonTerminalIndex[newNonTerminal1.getName()] = newNonTerminal1
                                        else:
                                            newNonTerminal1 = newNonTerminalIndex[newNonTerminalName1]
                                                    
                                        newNonTerminalName2 = InterNonTerminal.generateName(qiOutTrans.getSucc().getName(), V2, qprime.getName())
                                        # place causing problem of repeat productions: V1->V2, qi->qprime
                                        if newNonTerminalName2 not in newNonTerminalIndex:
                                            utils.debug('newNonTerminal2: %s not in newNonTerminalIndex' % newNonTerminalName2)
                                            newNonTerminal2 = InterNonTerminal(qiOutTrans.getSucc().getName(), V2, qprime.getName())
                                            newNonTerminalQueue.append(newNonTerminal2)                                                
                                            newNonTerminalIndex[newNonTerminal2.getName()] = newNonTerminal2
                                        else:
                                            newNonTerminal2 = newNonTerminalIndex[newNonTerminalName2]                                                    
                                        #utils.debug('newNonTerminalQueue: '+','.join(map(str, newNonTerminalQueue)))        
                                        newRightHandSide = [newNonTerminalIndex[u0], newNonTerminal1, newNonTerminalIndex[u1], newNonTerminal2]
                                        newProduction = Production(newLeftHandSide, newRightHandSide)  
                                        newProductions.append(newProduction)
                                        #utils.debug('newProduction: %s' % newProduction)
                                        
            
            #if count >= 2: break
        # end of generating productions 
        utils.debug('\n'.join(map(str, newProductions)))
        
        utils.info('Before remove productions containing non-available NT: (#NT=%d, #PROD=%d)'
               % (len(newNonTerminalIndex), len(newProductions)))
        
        # 3. delete productions whose rightHandSide contains nonTerminals not having productions
        newProductionsKept = [] 
        nonTerminalsHaveProductionIndex = dict()
        for p in newProductions:
            nonTerminalsHaveProductionIndex[p.leftHandSide()] = 1
        
        for p in newProductions:
            toKeep = 1
            for t in p.rightHandSide():
                if isinstance(t, NonTerminal):
                    if t not in nonTerminalsHaveProductionIndex:
                        toKeep = 0
                        break
            if toKeep: newProductionsKept.append(p)    
        
        return Grammar(newAxiom, newProductionsKept)

    ###############################################################################       

    def minimize(self):
        """
        Minimize by deleting non-accessible and non-productive nonTerminals, 
        and associated productions
        """
        
        # Starting from axiom, compute accessible nonterminals 
        # And compute connected directed graph between nonterminal nodes.
        g = DiGraph()

        nqueue = [self._axiom]
        # ('p':producible, 'a':accessible)
        accessIndex = {self._axiom.getName():{'a':False,'p':False}} 
        
        while len(nqueue) > 0:
            nt = nqueue.pop(0)
            ps = self.productions(nt)
            for p in ps:
                     
                accessIndex[nt.getName()]['a'] = True # accessible
                if (len(p.rightHandSide()) == 1 
                    and isinstance(p.rightHandSide()[0], Terminal)):
                    accessIndex[nt.getName()]['p'] = True # producible
                
                nt_names = []
                for e in p.rightHandSide():
                    if isinstance(e, NonTerminal):
                        nt_names.append(e.getName())
                        
                        if e.getName() not in accessIndex:
                            nqueue.append(e)
                            accessIndex[e.getName()] = {'a':False,'p':False}

                g.add_edge(p.leftHandSide().getName(), ".".join(nt_names))

        utils.debug(accessIndex)
        utils.debug("\n".join(map(str, g.edges())))

        # Starting from Terminal nodes, compute producible nonterminals 
        nt_p = [nt_name for nt_name in list(accessIndex.keys()) 
                if accessIndex[nt_name]['p']]
        while len(nt_p) > 0:
            nt_name = nt_p.pop(0)
            for pred in g.predecessors(nt_name):
                if accessIndex[pred] and not accessIndex[pred]['p']:
                    accessIndex[pred]['p'] = True
                    nt_p.append(pred)
        
        # For nodes with multiple NT, like S5->aS6uS7
        for node in g.nodes():
            if "." in node:
                (a, b) = node.split(".")
                if accessIndex[a]['p'] and accessIndex[b]['p']:
                    preds = g.predecessors(node)
                    for pred in preds:
                        accessIndex[pred]['p'] = True
                    nt_p += preds

        # Update when new producible nodes are added.
        while len(nt_p) > 0:
            nt_name = nt_p.pop(0)
            for pred in g.predecessors(nt_name):
                if accessIndex[pred] and not accessIndex[pred]['p']:
                    accessIndex[pred]['p'] = True
                    nt_p.append(pred)

        utils.debug(accessIndex)
        utils.info('Size of productions before minimization: %d'
                   % len(self._productions))

        i = 0
        # Keep only productions being accessible and producible
        while i < len(self._productions):
            left_name = self._productions[i].leftHandSide().getName()
            is_producible = True
            for e in self._productions[i].rightHandSide():
                if (e.getName() in accessIndex 
                    and not accessIndex[e.getName()]['p']):
                    is_producible = False

            if (left_name not in accessIndex 
                or not accessIndex[left_name]['a']
                or not is_producible):
                self._productions.pop(i)
            else:
                i += 1

        utils.info('Size of productions after minimization: %d'
                   % len(self._productions))

        self._cleanRepeatProductions()
        self._leftHandSideIndex  = dict() #'_leftHandSide' => [production, ]
        self._rightHandSideIndex = dict() #'_rightHandSide[0]' => [production,]
        self._index()                     # do indexing
            
###############################################################################   
